{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Majority Element"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #hash-table #divide-and-conquer #counting #sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #哈希表 #分治 #计数 #排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: majorityElement"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #多数元素"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个大小为 <code>n</code><em> </em>的数组&nbsp;<code>nums</code> ，返回其中的多数元素。多数元素是指在数组中出现次数 <strong>大于</strong>&nbsp;<code>⌊ n/2 ⌋</code>&nbsp;的元素。</p>\n",
    "\n",
    "<p>你可以假设数组是非空的，并且给定的数组总是存在多数元素。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例&nbsp;1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [3,2,3]\n",
    "<strong>输出：</strong>3</pre>\n",
    "\n",
    "<p><strong>示例&nbsp;2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [2,2,1,1,1,2,2]\n",
    "<strong>输出：</strong>2\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "<strong>提示：</strong>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>n == nums.length</code></li>\n",
    "\t<li><code>1 &lt;= n &lt;= 5 * 10<sup>4</sup></code></li>\n",
    "\t<li><code>-10<sup>9</sup> &lt;= nums[i] &lt;= 10<sup>9</sup></code></li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>进阶：</strong>尝试设计时间复杂度为 O(n)、空间复杂度为 O(1) 的算法解决此问题。</p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [majority-element](https://leetcode.cn/problems/majority-element/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [majority-element](https://leetcode.cn/problems/majority-element/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[3,2,3]', '[2,2,1,1,1,2,2]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def majorityElement(self, nums: List[int]) -> List[int]:\n",
    "        return [num for num in set(nums) if nums.count(num) > len(nums) // 3]\n",
    "        # can you think of there must be only two nums in the result??\n",
    "    \n",
    "#         # a list of majority elements\n",
    "#         majority = []\n",
    "        \n",
    "#         # threshold for majority validation and verification\n",
    "#         threshold = len(nums) // 3\n",
    "        \n",
    "#         # Record for possible majority candidates, at most two majority elements is allowed by math-proof.\n",
    "#         candidate = [0, 0]\n",
    "        \n",
    "#         # Voting for majority candidates\n",
    "#         voting = [0, 0]\n",
    "        \n",
    "#         ## Step_#1:\n",
    "#         # Find possible majority candidates\n",
    "#         for number in nums:\n",
    "            \n",
    "#             if number == candidate[0]:\n",
    "#                 # up vote to first candidate\n",
    "#                 voting[0] += 1\n",
    "                \n",
    "#             elif number == candidate[1]:\n",
    "#                 # up vote to second candidate\n",
    "#                 voting[1] += 1\n",
    "            \n",
    "#             elif not voting[0]:\n",
    "#                 # set first candidate\n",
    "#                 candidate[0] = number\n",
    "#                 voting[0] = 1\n",
    "                \n",
    "#             elif not voting[1]:\n",
    "#                 # set second candidate\n",
    "#                 candidate[1] = number\n",
    "#                 voting[1] = 1\n",
    "                \n",
    "#             else:\n",
    "#                 # down vote if mis-match\n",
    "#                 voting[0] -= 1\n",
    "#                 voting[1] -= 1\n",
    "        \n",
    "        \n",
    "#         ## Step_#2:\n",
    "#         # Validation:\n",
    "#         voting = [0, 0]\n",
    "        \n",
    "#         for number in nums:\n",
    "            \n",
    "#             if number == candidate[0]:\n",
    "#                 # update up vote for first candidate\n",
    "#                 voting[0] += 1\n",
    "                \n",
    "#             elif number == candidate[1]:\n",
    "#                 # update up vote for second candidate\n",
    "#                 voting[1] += 1\n",
    "        \n",
    "        \n",
    "#         for i, vote in enumerate(voting):\n",
    "            \n",
    "#             # Verify majority by threshold\n",
    "#             if vote > threshold:\n",
    "#                 majority.append( candidate[i] )\n",
    "            \n",
    "            \n",
    "#         return majority\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def majorityElement(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        n = len(nums)\n",
    "        count = [0, 0]\n",
    "        element = [None, None]\n",
    "        for num in nums:\n",
    "            if num == element[0]:\n",
    "                count[0] += 1\n",
    "            elif num == element[1]:\n",
    "                count[1] += 1\n",
    "            elif count[0] == 0:\n",
    "                count[0] = 1\n",
    "                element[0] = num\n",
    "            elif count[1] == 0:\n",
    "                count[1] = 1\n",
    "                element[1] = num\n",
    "            else:\n",
    "                count[0] -= 1\n",
    "                count[1] -= 1\n",
    "        res = [e for e in element if nums.count(e) > n // 3]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def majorityElement(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        dic={}\n",
    "        value=[]\n",
    "        print(math.floor(len(nums)/3))\n",
    "        if len(nums)==1:\n",
    "            return nums\n",
    "        for i in nums:\n",
    "            if i in dic and i in value:\n",
    "                continue\n",
    "            if i in dic:\n",
    "                dic[i]=dic[i]+1\n",
    "            else:\n",
    "                dic[i]=1\n",
    "            if dic[i]>math.floor(len(nums)/3):\n",
    "                    value.append(i)\n",
    "        return value"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def majorityElement(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        d = collections.Counter(nums)\n",
    "        return [k for k, v in d.items() if v > len(nums) / 3]\n",
    "\n",
    "\n",
    "# class Solution:\n",
    "#     def majorityElement(self, nums):\n",
    "#         if len(nums) < 2:\n",
    "#             return nums\n",
    "#         a, b, ac, bc = nums[0], nums[0], 0, 0\n",
    "#         for num in nums:\n",
    "#             if num == a:\n",
    "#                 ac += 1\n",
    "#             elif num == b:\n",
    "#                 bc += 1\n",
    "#             else:\n",
    "#                 if ac == 0:\n",
    "#                     a = num\n",
    "#                     ac = 1\n",
    "#                 elif bc == 0:\n",
    "#                     b = num\n",
    "#                     bc = 1\n",
    "#                 else:\n",
    "#                     ac -= 1\n",
    "#                     bc -= 1\n",
    "#         if a == b:\n",
    "#             return [a]\n",
    "#         else:\n",
    "#             l = len(nums) // 3\n",
    "#             res = []\n",
    "#             if nums.count(a) > l:\n",
    "#                 res.append(a)\n",
    "#             if nums.count(b) > l:\n",
    "#                 res.append(b)\n",
    "#             return res\n",
    "#             # ac = bc = 0\n",
    "#             # for num in nums:\n",
    "#             #     if num == a:\n",
    "#             #         ac += 1\n",
    "#             #     elif num == b:\n",
    "#             #         bc += 1\n",
    "#             # return ([a] if ac > l else []) + ([b] if bc > l else [])\n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def majorityElement(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)//3\n",
    "        d = {}\n",
    "        for i in nums:\n",
    "            if i in d.keys():\n",
    "                d[i] += 1\n",
    "            else:\n",
    "                d[i] = 1\n",
    "        result = []\n",
    "        for key,value in d.items():\n",
    "            if value > n:\n",
    "                result.append(key)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def majorityElement(self, nums):\n",
    "#         \"\"\"\n",
    "#         :type nums: List[int]\n",
    "#         :rtype: List[int]\n",
    "#         \"\"\"\n",
    "#         x = len(nums) // 3\n",
    "#         res = []\n",
    "#         d = collections.Counter(nums)\n",
    "#         for k, v in d.items():\n",
    "#             if v > x:\n",
    "#                 res.append(k)\n",
    "#                 # if len(res) == 2:\n",
    "#                 #     return res\n",
    "#         return res\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def majorityElement(self, nums):\n",
    "        if len(nums) < 2:\n",
    "            return nums\n",
    "        a, b, ac, bc = nums[0], nums[0], 0, 0\n",
    "        for num in nums:\n",
    "            if num == a:\n",
    "                ac += 1\n",
    "            elif num == b:\n",
    "                bc += 1\n",
    "            else:\n",
    "                if ac == 0:\n",
    "                    a = num\n",
    "                    ac = 1\n",
    "                elif bc == 0:\n",
    "                    b = num\n",
    "                    bc = 1\n",
    "                else:\n",
    "                    ac -= 1\n",
    "                    bc -= 1\n",
    "        if a == b:\n",
    "            return [a]\n",
    "        else:\n",
    "            l = len(nums) // 3\n",
    "            res = []\n",
    "            if nums.count(a) > l:\n",
    "                res.append(a)\n",
    "            if nums.count(b) > l:\n",
    "                res.append(b)\n",
    "            return res\n",
    "            # ac = bc = 0\n",
    "            # for num in nums:\n",
    "            #     if num == a:\n",
    "            #         ac += 1\n",
    "            #     elif num == b:\n",
    "            #         bc += 1\n",
    "            # return ([a] if ac > l else []) + ([b] if bc > l else [])\n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def majorityElement(self, nums):\n",
    "        a = sorted(nums)\n",
    "        n = len(a)\n",
    "        if n == 1 or n == 0: return(nums)\n",
    "        node1 = a[int(n/3)]\n",
    "        node2 = a[round(2*n/3)]\n",
    "        \n",
    "        if sum([iter1 == node1 for iter1 in nums]) > n/3:\n",
    "            if sum([iter2 == node2 for iter2 in nums])  > n/3 and node1 - node2 != 0:\n",
    "                return([node1,node2])\n",
    "            else:\n",
    "                return([node1])\n",
    "        else:\n",
    "            if sum([iter2 == node2 for iter2 in nums]) > n/3:\n",
    "                return([node2])\n",
    "            else:\n",
    "                return([])\n",
    "            \n",
    "                \n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def majorityElement(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        num_set = set(nums)\n",
    "        res = {num:0 for num in num_set}\n",
    "        length = len(nums)//3\n",
    "        for elem in nums:\n",
    "            res[elem]+=1\n",
    "        answer = [key for key, value in res.items() if value>length]\n",
    "        return answer\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def majorityElement(self, nums: 'List[int]') -> 'List[int]':\n",
    "        a,b,ca,cb = None,None,0,0\n",
    "        for n in nums:\n",
    "            if n == a:\n",
    "                ca += 1\n",
    "            elif n == b:\n",
    "                cb += 1\n",
    "            else:\n",
    "                if ca == 0:\n",
    "                    a = n\n",
    "                    ca = 1\n",
    "                elif cb == 0:\n",
    "                    b = n\n",
    "                    cb = 1\n",
    "                else:\n",
    "                    ca -= 1\n",
    "                    cb -= 1\n",
    "        ca,cb = 0,0\n",
    "        minNum = math.floor(len(nums)/3)\n",
    "        for n in nums:\n",
    "            if a == n:\n",
    "                ca += 1\n",
    "            elif b == n:\n",
    "                cb += 1\n",
    "        result = []\n",
    "        if ca > minNum:\n",
    "            result.append(a)\n",
    "        if cb > minNum:\n",
    "            result.append(b)\n",
    "        return result\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "\n",
    "class Solution:\n",
    "#     def majorityElement(self, nums: 'List[int]') -> 'List[int]':\n",
    "#         if len(nums) == 1: return nums\n",
    "#         if len(nums) == 2:\n",
    "#             if nums[0] == nums[1]: return [nums[0]]\n",
    "#             else: return nums\n",
    "        \n",
    "#         res = []\n",
    "#         c = dict(Counter(nums))\n",
    "#         for key in c.keys():\n",
    "#             if c[key] > len(nums) // 3:\n",
    "#                 res.append(key)\n",
    "#         return res\n",
    "    \n",
    "    # find three different votes and hide them\n",
    "#     def majorityElement(self, nums):\n",
    "#         if not nums: return []\n",
    "        \n",
    "#         c = Counter()\n",
    "#         for num in nums:\n",
    "#             c[num] += 1\n",
    "#             if len(c) == 3:\n",
    "#                 c -= Counter(set(c))\n",
    "#         return [num for num in c if nums.count(num) > len(nums) // 3]\n",
    "    \n",
    "    # Boyer-Moore voting algo\n",
    "    def majorityElement(self, nums):\n",
    "        if not nums: return []\n",
    "        \n",
    "        ca, cb, cana, canb = 0, 0, 0, 1\n",
    "        for n in nums:\n",
    "            if n == cana:\n",
    "                ca += 1\n",
    "            elif n == canb:\n",
    "                cb += 1\n",
    "            elif ca == 0:\n",
    "                ca, cana = 1, n\n",
    "            elif cb == 0:\n",
    "                cb, canb = 1, n\n",
    "            else:\n",
    "                ca, cb = ca - 1, cb - 1\n",
    "            \n",
    "        return [n for n in (cana, canb) if nums.count(n) > len(nums) // 3]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def majorityElement(self, nums: List[int]) -> List[int]:\n",
    "        from itertools import groupby\n",
    "        res = []\n",
    "        n = len(nums)/3\n",
    "        for k, v in groupby(sorted(nums)):\n",
    "            if len(list(v)) > n:\n",
    "                res.append(k)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def majorityElement(self, nums: List[int]) -> List[int]:\n",
    "        length=len(nums)\n",
    "        if length==0:\n",
    "            return []\n",
    "        countA=0\n",
    "        countB=0\n",
    "        A=None\n",
    "        B=None\n",
    "        for item in nums:\n",
    "            if item==A:\n",
    "                countA+=1\n",
    "            elif item==B:\n",
    "                countB+=1\n",
    "            elif countA==0:\n",
    "                A=item\n",
    "                countA+=1\n",
    "            elif countB==0:\n",
    "                B=item\n",
    "                countB+=1\n",
    "            else:\n",
    "                countA-=1\n",
    "                countB-=1\n",
    "        res=[]\n",
    "        countA=0\n",
    "        countB=0\n",
    "        for item in nums:\n",
    "            if item==A:\n",
    "                countA+=1\n",
    "            elif item==B:\n",
    "                countB+=1\n",
    "        print(A,B,countA,countB)\n",
    "        if countA>len(nums)//3:\n",
    "            res.append(A)\n",
    "        if countB>len(nums)//3:\n",
    "            res.append(B)\n",
    "        return res\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def majorityElement(self, nums: list) -> list:\n",
    "        from math import floor\n",
    "        if len(nums) == 0 or len(nums)==1:\n",
    "            return nums\n",
    "        candidate_x, candidate_y = 0, 0\n",
    "        count_x, count_y = 0, 0\n",
    "        for num in nums:\n",
    "            if num == candidate_x:\n",
    "                count_x += 1\n",
    "                continue\n",
    "            if num == candidate_y:\n",
    "                count_y += 1\n",
    "                continue\n",
    "            if count_x == 0:\n",
    "                candidate_x = num\n",
    "                count_x += 1\n",
    "                continue\n",
    "            if count_y == 0:\n",
    "                candidate_y = num\n",
    "                count_y += 1\n",
    "                continue\n",
    "            if candidate_x!=num and candidate_y!=num:\n",
    "                count_x -= 1\n",
    "                count_y -= 1\n",
    "        i, j = 0, 0\n",
    "        for num in nums:\n",
    "            if num == candidate_x:\n",
    "                i += 1\n",
    "            if num == candidate_y:\n",
    "                j += 1\n",
    "        ans = []\n",
    "        if candidate_x == candidate_y and i > floor(len(nums)/3):\n",
    "            return [candidate_y]\n",
    "        if i > floor(len(nums)/3):\n",
    "            ans.append(candidate_x)\n",
    "        if j > floor(len(nums)/3):\n",
    "            ans.append(candidate_y)\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def solve(nums):\n",
    "    data = dict()\n",
    "    count = len(nums) // 3\n",
    "    for n in nums:\n",
    "        if n in data:\n",
    "            data[n] += 1\n",
    "        else:\n",
    "            data[n] = 1\n",
    "    ans = []\n",
    "    for item in data.items():\n",
    "        if item[1] > count:\n",
    "            ans.append(item[0])\n",
    "\n",
    "    return ans\n",
    "\n",
    "class Solution:\n",
    "    def majorityElement(self, nums: List[int]) -> List[int]:\n",
    "        return solve(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def majorityElement(self, nums):\n",
    "        count = 0\n",
    "        nums.sort()\n",
    "        for index,val in enumerate(nums):\n",
    "            if (index+len(nums)//3)<len(nums):\n",
    "                if nums[index]==nums[index+len(nums)//3]:\n",
    "                    if nums[index] not in nums[:count]:\n",
    "                        nums[count]=nums[index]\n",
    "                        count = count + 1\n",
    "        return nums[:count]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def majorityElement(self, nums: List[int]) -> List[int]:\n",
    "        numscount = collections.Counter(nums)\n",
    "        ans = []\n",
    "        targetcount = len(nums)/3\n",
    "        for num in numscount:\n",
    "            if numscount[num]>targetcount:\n",
    "                ans.append(num)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def majorityElement(self, nums: List[int]) -> List[int]:\n",
    "        i, j, k, res, temp = -1, 0, 1, set(), []\n",
    "        while True:\n",
    "            for i in range(i+1, len(nums)):\n",
    "                if nums[i] not in res and i not in temp:\n",
    "                    print(i, nums[i])\n",
    "                    res.add(nums[i])\n",
    "                    break\n",
    "\n",
    "            for j in range(j+1, len(nums)):\n",
    "                if nums[j] not in res and j not in temp:\n",
    "                    res.add(nums[j])\n",
    "                    break\n",
    "\n",
    "            for k in range(k+1, len(nums)):\n",
    "                if nums[k] not in res and k not in temp:\n",
    "                    res.add(nums[k])\n",
    "                    break\n",
    "\n",
    "            if len(res) == 3:  \n",
    "                temp.extend([i, j, k]) \n",
    "                res.clear()\n",
    "            else:\n",
    "                break\n",
    "\n",
    "        return [m for m in res if nums.count(m)>len(nums)//3]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def majorityElement(self, nums: List[int]) -> List[int]:\n",
    "        if not nums:\n",
    "            return []\n",
    "        n1 = n2 = nums[0]\n",
    "        c1 = c2 = 0\n",
    "        n = len(nums)\n",
    "        for i in range(n):\n",
    "            if n1 == nums[i]:\n",
    "                c1 += 1\n",
    "                continue\n",
    "            if n2 == nums[i]:\n",
    "                c2 += 1\n",
    "                continue\n",
    "            if c1 == 0:\n",
    "                n1 = nums[i]\n",
    "                c1 = 1\n",
    "                continue\n",
    "            if c2 == 0:\n",
    "                n2 = nums[i]\n",
    "                c2 = 1\n",
    "                continue\n",
    "            c1 -= 1\n",
    "            c2 -= 1\n",
    "        c1 = c2 = 0\n",
    "        for num in nums:\n",
    "            if num == n1:\n",
    "                c1 += 1\n",
    "            elif num == n2:\n",
    "                c2 += 1\n",
    "        res = []\n",
    "        if c1 > n // 3:\n",
    "            res.append(n1)\n",
    "        if c2 > n // 3:\n",
    "            res.append(n2)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def majorityElement(self, nums: List[int]) -> List[int]:\n",
    "        rlist = []\n",
    "        counter = set(nums)\n",
    "        for i in counter:\n",
    "            if nums.count(i) > (len(nums)/3):\n",
    "                rlist.append(i)\n",
    "        return rlist"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def majorityElement(self, nums: List[int]) -> List[int]:\n",
    "        count_a, count_b, a, b = 0, 0, 0, 0\n",
    "        for num in nums:\n",
    "            if (count_a == 0 or num == a) and num != b:  # num加入a队\n",
    "                count_a += 1\n",
    "                a = num\n",
    "            elif count_b == 0 or num == b:  # num加入b队\n",
    "                count_b += 1\n",
    "                b = num\n",
    "            else:   # num既不是a队也不是b队，此时该num抵消掉a和b中的一个数\n",
    "                count_a -= 1\n",
    "                count_b -= 1\n",
    "        # 剩下的a和b是nums数组中数量最多的两个元素\n",
    "        count_a = 0\n",
    "        count_b = 0\n",
    "        for num in nums:\n",
    "            if num == a:\n",
    "                count_a += 1\n",
    "            elif num == b:\n",
    "                count_b += 1\n",
    "        res = []\n",
    "        if count_a > (len(nums)//3):\n",
    "            res.append(a)\n",
    "        if count_b > (len(nums)//3):\n",
    "            res.append(b)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def majorityElement(self, nums: List[int]) -> List[int]:\n",
    "        ans = []\n",
    "        element1, element2 = 0, 0\n",
    "        vote1, vote2 = 0, 0\n",
    "\n",
    "        for num in nums:\n",
    "            # 如果该元素为第一个元素，则计数加1\n",
    "            if vote1 > 0 and num == element1:\n",
    "                vote1 += 1\n",
    "            # 如果该元素为第二个元素，则计数加1\n",
    "            elif vote2 > 0 and num == element2:\n",
    "                vote2 += 1\n",
    "            # 选择第一个元素\n",
    "            elif vote1 == 0:\n",
    "                element1 = num\n",
    "                vote1 += 1\n",
    "            # 选择第二个元素\n",
    "            elif vote2 == 0:\n",
    "                element2 = num\n",
    "                vote2 += 1\n",
    "            # 如果三个元素均不相同，则相互抵消1次\n",
    "            else:\n",
    "                vote1 -= 1\n",
    "                vote2 -= 1\n",
    "\n",
    "        cnt1, cnt2 = 0, 0\n",
    "        for num in nums:\n",
    "            if vote1 > 0 and num == element1:\n",
    "                cnt1 += 1\n",
    "            if vote2 > 0 and num == element2:\n",
    "                cnt2 += 1        \n",
    "        # 检测元素出现的次数是否满足要求\n",
    "        if vote1 > 0 and cnt1 > len(nums) / 3:\n",
    "            ans.append(element1)\n",
    "        if vote2 > 0 and cnt2 > len(nums) / 3:\n",
    "            ans.append(element2)\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def majorityElement(self, nums: List[int]) -> List[int]:\n",
    "        k = len(nums) // 3\n",
    "        cnt = {}\n",
    "        ans = []\n",
    "        for i in nums:\n",
    "            if i in cnt:\n",
    "                cnt[i] += 1\n",
    "            else:\n",
    "                cnt[i] = 1\n",
    "        for i in cnt:\n",
    "            if cnt[i] > k:\n",
    "                ans.append(i)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def majorityElement(self, nums: List[int]) -> List[int]:\n",
    "\n",
    "        '''\n",
    "        dic = {}\n",
    "        base = len(nums) / 3\n",
    "        for i in range(len(nums)):\n",
    "            dic[nums[i]] = dic.get(nums[i],0) + 1\n",
    "        res = []\n",
    "        for d in dic.keys():\n",
    "            if dic[d] > base:\n",
    "                res.append(d)\n",
    "        \n",
    "        return res\n",
    "        '''\n",
    "\n",
    "        # 摩尔投票法\n",
    "        base = len(nums) / 3\n",
    "        candidate1,candidate2 = 0,0\n",
    "        vote1,vote2 = 0,0\n",
    "\n",
    "        for d in nums:\n",
    "            if d == candidate1:\n",
    "                vote1 += 1\n",
    "            elif d == candidate2:\n",
    "                vote2 += 1\n",
    "            elif vote1 == 0:\n",
    "                candidate1 = d\n",
    "                vote1 = 1\n",
    "            elif vote2 == 0:\n",
    "                candidate2 = d\n",
    "                vote2 = 1\n",
    "            else:\n",
    "                vote1 -= 1\n",
    "                vote2 -= 1\n",
    "            \n",
    "        vote1,vote2 = 0,0\n",
    "        for d in nums:\n",
    "            if d == candidate1:\n",
    "                vote1 += 1\n",
    "            if d == candidate2:\n",
    "                vote2 += 1\n",
    "        res = []\n",
    "        if vote1 > base:\n",
    "            res.append(candidate1)\n",
    "        if vote2 > base:\n",
    "            res.append(candidate2)\n",
    "        return list(set(res))\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def majorityElement(self, nums: List[int]) -> List[int]:\n",
    "        dic={}\n",
    "        for i in nums:\n",
    "            try:\n",
    "                dic[i]+=1\n",
    "            except:\n",
    "                dic[i]=1\n",
    "        ans=[]\n",
    "        for key in dic.keys():\n",
    "            if dic[key]>len(nums)//3:\n",
    "                ans.append(key)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def majorityElement(self, nums: List[int]) -> List[int]:\r\n",
    "        d = dict()        \r\n",
    "        for num in nums:\r\n",
    "            if num not in d:\r\n",
    "                d[num] = 1\r\n",
    "            else:\r\n",
    "                d[num] += 1\r\n",
    "        l = []\r\n",
    "        for k,v in d.items():\r\n",
    "            if v > len(nums) // 3:\r\n",
    "                l.append(k)\r\n",
    "        return l\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def majorityElement(self, nums: List[int]) -> List[int]:\n",
    "        return [n for n, v in Counter(nums).items() if v > len(nums) // 3]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def majorityElement(self, nums: List[int]) -> List[int]:\n",
    "        nums=sorted(nums)\n",
    "        n=len(nums)\n",
    "        if n<3:\n",
    "            r=[]\n",
    "            for i in nums:\n",
    "                if i not in r:\n",
    "                    r.append(i)\n",
    "            return r\n",
    "        index=n//3\n",
    "        a=nums[index]\n",
    "        b=nums[n-index-1]\n",
    "        r=[]\n",
    "        if nums.count(a)>len(nums)//3:\n",
    "            r.append(a)\n",
    "        if nums.count(b)>len(nums)//3:\n",
    "            if b not in r:\n",
    "                r.append(b)\n",
    "        return r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def majorityElement(self, nums: List[int]) -> List[int]:\n",
    "        length = len(nums)\n",
    "        ans = dict()\n",
    "        for i in range(length):\n",
    "            if nums[i] not in ans:\n",
    "                ans[nums[i]] = 1\n",
    "            else:\n",
    "                ans[nums[i]] += 1\n",
    "        nums.clear()\n",
    "        for key, value in ans.items():\n",
    "            if value > length // 3:\n",
    "                nums.append(key)\n",
    "        return nums"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def majorityElement(self, nums: List[int]) -> List[int]:\n",
    "        ans=[]\n",
    "        n= len(nums)\n",
    "        dict =  {}\n",
    "        for i in range(n):\n",
    "            if nums[i] not in dict:\n",
    "                dict[nums[i]] =1\n",
    "            else:\n",
    "                dict[nums[i]] +=1\n",
    "\n",
    "        for x in dict:\n",
    "            if(dict[x]>n/3):\n",
    "                ans.append(x)\n",
    "            \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def majorityElement(self, nums: List[int], k: int = 3) -> List[int]:\n",
    "        counter = [[0, 0] for _ in range(k-1)]\n",
    "        for x in nums:\n",
    "            replace = False\n",
    "            j = -1\n",
    "            for i in range(k-1):\n",
    "                if x == counter[i][0]:\n",
    "                    counter[i][1] += 1\n",
    "                    replace = False\n",
    "                    j = i\n",
    "                    break\n",
    "                elif counter[i][1] == 0:\n",
    "                    replace = True\n",
    "                    j = i\n",
    "            if replace:\n",
    "                counter[j][0] = x\n",
    "                counter[j][1] = 1\n",
    "            elif j == -1:\n",
    "                for i in range(k-1):\n",
    "                    counter[i][1] -= 1\n",
    "        \n",
    "        for i in range(k-1):\n",
    "            counter[i][1] = 0\n",
    "        for x in nums:\n",
    "            for i in range(k-1):\n",
    "                if x == counter[i][0]:\n",
    "                    counter[i][1] += 1\n",
    "                    break\n",
    "\n",
    "        ans = []\n",
    "        lim = len(nums) // k\n",
    "        for x, c in counter:\n",
    "            if c > lim:\n",
    "                ans.append(x)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def majorityElement(self, nums: List[int]) -> int:\n",
    "        # for num in set(nums):\n",
    "        #     if nums.count(num) > int(len(nums) / 2):\n",
    "        #         return num\n",
    "            \n",
    "        # more simple\n",
    "        nums.sort()\n",
    "        return nums[len(nums)//2]\n",
    "    \n",
    "#         count = 0\n",
    "#         candidate = None\n",
    "\n",
    "#         for num in nums:\n",
    "#             if count == 0:\n",
    "#                 candidate = num\n",
    "#             count += (1 if num == candidate else -1)\n",
    "\n",
    "#         return candidate\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def majorityElement(self, nums: 'List[int]') -> 'int':\n",
    "        nums.sort()\n",
    "        middle = int(len(nums)/2)\n",
    "        print(middle)\n",
    "        s_num = nums[middle]\n",
    "        \n",
    "        number = 0\n",
    "        for num in nums:\n",
    "            if num==s_num:\n",
    "                number += 1\n",
    "        \n",
    "        if number>middle:\n",
    "            return s_num\n",
    "        \n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def majorityElement(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        m, c = 0, 0\n",
    "        for n in nums:\n",
    "            if not c:\n",
    "                m, c = n, 1\n",
    "            elif n == m:\n",
    "                c += 1\n",
    "            else:\n",
    "                c -= 1            \n",
    "        return m"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def majorityElement(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        n=len(nums)\n",
    "        candidate, cnt = None, 0\n",
    "        num = 0\n",
    "        for i in nums:\n",
    "            if cnt == 0:\n",
    "                candidate = i\n",
    "                cnt += 1\n",
    "                num = 0\n",
    "            else:\n",
    "                if candidate == i:\n",
    "                    cnt += 1\n",
    "                    num += 1\n",
    "                else:\n",
    "                    cnt -= 1\n",
    "        print(num)\n",
    "        return candidate\n",
    "        \n",
    "        # cnt = nums.count(candidate)\n",
    "        # return candidate if cnt>n//2 else None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def majorityElement(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        dic = {}\n",
    "        a = len(nums)//2\n",
    "        for i in nums:\n",
    "            if i not in dic:\n",
    "                dic[i] =1\n",
    "            else:\n",
    "                dic[i] +=1\n",
    "            \n",
    "        for i in dic:\n",
    "            if dic[i] > a:\n",
    "                return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def majorityElement(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        nums.sort()\n",
    "        return nums[len(nums)//2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def majorityElement(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        return sorted(nums)[len(nums) // 2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def majorityElement(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        dic = {}\n",
    "        max_n = 0\n",
    "        max_key = -1\n",
    "        for n in nums:\n",
    "            if not dic.get(n):\n",
    "                dic[n] = 1\n",
    "            else:\n",
    "                dic[n] += 1\n",
    "            if max_n < dic[n]:\n",
    "                max_key = n\n",
    "                max_n = dic[n]\n",
    "        return max_key\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def majorityElement(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        return self.func2(nums)\n",
    "        \n",
    "    def func1(self,nums):\n",
    "        nums.sort()\n",
    "        return nums[len(nums)//2]\n",
    "        \n",
    "    def func2(self,nums):\n",
    "        count = 1\n",
    "        first = nums[0]\n",
    "        for item in nums[1:]:\n",
    "            if item == first:\n",
    "                count += 1\n",
    "            else:\n",
    "                count -= 1\n",
    "            if count == 0:\n",
    "                first = item\n",
    "                count +=1\n",
    "        return first"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def majorityElement(self, nums: 'List[int]') -> 'int':\n",
    "        length = len(nums)\n",
    "        half = length / 2\n",
    "        current = 0\n",
    "        vote = 0\n",
    "        for x in nums:\n",
    "            if vote == 0:\n",
    "                current = x\n",
    "                vote = 1\n",
    "            else:\n",
    "                if x == current:\n",
    "                    vote += 1\n",
    "                else:\n",
    "                    vote -= 1\n",
    "            print(current, vote)\n",
    "        return current"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "\n",
    "class Solution:\n",
    "    def majorityElement(self, nums: 'List[int]') -> 'int':\n",
    "        if not len(nums): return 0\n",
    "        \n",
    "        c = dict(Counter(nums))\n",
    "        return max(c, key=c.get)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def majorityElement(self, nums: 'List[int]') -> 'int':\n",
    "        if len(nums) == 1:\n",
    "            return nums[0]\n",
    "        major = None\n",
    "        count = 0\n",
    "        for i in nums:\n",
    "            if major == None:\n",
    "                major = i\n",
    "                count += 1\n",
    "            elif i != major:\n",
    "                count -= 1\n",
    "                if count == 0:\n",
    "                    major = None\n",
    "            else:\n",
    "                count += 1\n",
    "            \n",
    "        return major\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def majorityElement(self, nums) -> int:\n",
    "        d = 0\n",
    "        m = len(nums) // 2\n",
    "        for i in set(nums):\n",
    "            if nums.count(i) > m:\n",
    "                return i\n",
    "            elif nums.count(i) > nums.count(d):\n",
    "                d = i\n",
    "        return d"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def majorityElement(self, nums: List[int]) -> int:\n",
    "        res, count = 0, 0\n",
    "        for i in nums:\n",
    "            if count == 0:\n",
    "                res=i\n",
    "                count += 1\n",
    "            else:\n",
    "                count += (1 if res==i else -1)\n",
    "        if count > 0:\n",
    "            return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "class Solution:\n",
    "    def majorityElement(self, nums: List[int]) -> int:\n",
    "        c = Counter(nums)\n",
    "        c = sorted(c.items(), key=lambda x:x[1], reverse=True)\n",
    "        return c[0][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def majorityElement(self, nums: List[int]) -> int:\n",
    "        ret={}\n",
    "        for i in nums:\n",
    "            if not ret.get(i):\n",
    "               ret[i]=0 \n",
    "            ret[i]+=1\n",
    "            if ret[i] > len(nums)/2:\n",
    "                return i\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def majorityElement(self, nums: List[int]) -> int:\r\n",
    "        l = len(nums)/2\r\n",
    "        for num in set(nums):\r\n",
    "            i = 0\r\n",
    "            while num in nums:\r\n",
    "                nums.remove(num)\r\n",
    "                i += 1\r\n",
    "            if i > l:\r\n",
    "                return num\r\n",
    "\r\n",
    "\r\n",
    "\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def majorityElement(self, nums: List[int]) -> int:\n",
    "        if len(nums) <= 2:\n",
    "            return nums[0]\n",
    "        idx = 0\n",
    "        while idx < len(nums) - 1:\n",
    "            if nums[idx] != nums[idx+1]:\n",
    "                del nums[idx]\n",
    "                del nums[idx]\n",
    "                if idx > 0:\n",
    "                    idx -= 1\n",
    "            else:\n",
    "                idx += 1\n",
    "        return nums[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def majorityElement(self, nums: List[int]) -> int:\n",
    "        len_ = len(nums) / 2\n",
    "        nums_set = set(nums)\n",
    "        for i in nums_set:\n",
    "            if nums.count(i) > len_:\n",
    "                return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def majorityElement(self, nums: List[int]) -> int:\n",
    "        return collections.Counter(nums).most_common(1)[0][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def majorityElement(self, nums: List[int]) -> int:\r\n",
    "        # nums.sort()\r\n",
    "        # return nums[len(nums) // 2]\r\n",
    "        dic = {}\r\n",
    "        for i in nums:\r\n",
    "            if i in dic:\r\n",
    "                dic[i] = dic[i] + 1\r\n",
    "            else:\r\n",
    "                dic[i] = 1\r\n",
    "            if dic[i] > len(nums) // 2:\r\n",
    "                return i\r\n",
    "\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def majorityElement(self, nums, lo=0, hi=None):\n",
    "        def majority_element_rec(lo, hi):\n",
    "            # base case; the only element in an array of size 1 is the majority\n",
    "            # element.\n",
    "            if lo == hi:\n",
    "                return nums[lo]\n",
    "\n",
    "            # recurse on left and right halves of this slice.\n",
    "            mid = (hi-lo)//2 + lo\n",
    "            left = majority_element_rec(lo, mid)\n",
    "            right = majority_element_rec(mid+1, hi)\n",
    "\n",
    "            # if the two halves agree on the majority element, return it.\n",
    "            if left == right:\n",
    "                return left\n",
    "\n",
    "            # otherwise, count each element and return the \"winner\".\n",
    "            left_count = sum(1 for i in range(lo, hi+1) if nums[i] == left)\n",
    "            right_count = sum(1 for i in range(lo, hi+1) if nums[i] == right)\n",
    "\n",
    "            return left if left_count > right_count else right\n",
    "\n",
    "        return majority_element_rec(0, len(nums)-1)\n",
    "\n",
    "\n",
    "# 作者：LeetCode-Solution\n",
    "# 链接：https://leetcode-cn.com/problems/majority-element/solution/duo-shu-yuan-su-by-leetcode-solution/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def majorityElement(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        p = 1\n",
    "        while p < n:\n",
    "            if nums[p] == nums[0]:\n",
    "                p += 1\n",
    "            else:\n",
    "                nums.pop(p)\n",
    "                nums.pop(0)\n",
    "                p -= 1\n",
    "                n -= 2\n",
    "        return nums[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def majorityElement(self, nums: List[int]) -> int:\n",
    "        nums_half_len = len(nums) / 2.0\n",
    "        for num in set(nums):\n",
    "            num_count = 0\n",
    "            while num in nums:\n",
    "                num_count += 1\n",
    "                nums.remove(num)\n",
    "                if num_count > nums_half_len:\n",
    "                    return num"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def majorityElement(self, nums: List[int]) -> int:\n",
    "        dic=dict()\n",
    "        for i in nums:\n",
    "            if i in dic:\n",
    "                dic[i]+=1\n",
    "            else:\n",
    "                dic[i]=0\n",
    "        max_=-1\n",
    "        for key,value in dic.items():\n",
    "            if value>=max_:\n",
    "                max_=value\n",
    "                res=key\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def majorityElement(self, nums: List[int]) -> int:\n",
    "        res = nums[0]\n",
    "        cnt = 0\n",
    "        for num in nums:\n",
    "            if num == res:\n",
    "                cnt += 1\n",
    "            else:\n",
    "                cnt -= 1\n",
    "            if cnt < 0:\n",
    "                cnt = 1\n",
    "                res = num\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def majorityElement(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        count = dict()\n",
    "        for i in range(n):\n",
    "            if nums[i] not in count:\n",
    "                count.update({nums[i] : 1})\n",
    "            else:\n",
    "                count[nums[i]] = count.get(nums[i]) + 1\n",
    "        return max(count, key = lambda x : count[x])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def majorityElement(self, nums: List[int]) -> int:\n",
    "        from collections import Counter\n",
    "        d = Counter(nums)\n",
    "        for key in d:\n",
    "            if d[key] > len(nums) // 2:\n",
    "                return key\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def majorityElement(self, nums: List[int]) -> int:\n",
    "\n",
    "        candidata = None\n",
    "        count = 0\n",
    "        for num in nums:\n",
    "            if count == 0:\n",
    "                candidata = num\n",
    "            if candidata == num:\n",
    "                count += 1\n",
    "            else:\n",
    "                count -= 1\n",
    "        return candidata"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def majorityElement(self, nums: List[int]) -> int:\n",
    "        def getnum(nums, l ,r):\n",
    "            if l==r:\n",
    "                return nums[l]\n",
    "\n",
    "            m=(l+r)//2\n",
    "            left ,right = getnum(nums, l ,m), getnum(nums, m+1, r)\n",
    "            if left==right:\n",
    "                return left\n",
    "            \n",
    "            leftcount = sum([1 for i in range(l,m+1) if nums[i]==left])\n",
    "            rightcount = sum([1 for i in range(m+1, r+1) if nums[i]==right])\n",
    "            return left if leftcount>rightcount else right\n",
    "            \n",
    "        return getnum(nums, 0, len(nums)-1)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def majorityElement(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        return nums[len(nums) // 2]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def majorityElement(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        mid = len(nums)// 2\n",
    "        return nums[mid]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def majorityElement(self, nums: List[int]) -> int:\n",
    "        ans = None\n",
    "        ans_cnt = 0\n",
    "\n",
    "        for i in range(len(nums)):\n",
    "            if ans_cnt == 0:\n",
    "                ans = nums[i]\n",
    "                ans_cnt += 1\n",
    "            else:\n",
    "                if nums[i] == ans:\n",
    "                    ans_cnt += 1\n",
    "                else:\n",
    "                    ans_cnt -= 1\n",
    "        return ans\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
